//
// Created by ct on 2021/10/26.
//

#include "mvector.h"
#include <algorithm>
#include <iostream>
vector<vector<int>> Solution::threeSum(vector<int> &nums) {
    vector<vector<int>> r0;

    int len = (int )nums.size();
    if (len < 3 || nums.empty()) return r0;
    // 先进行排序
    std::sort(nums.begin(),nums.end());
    // 第一层循环，只关心选定的数据
    for (int i = 0; i < len && nums[i] < 1; ++i) {
        if (nums[i] > 0) return r0;
        if(i >0 && nums[i] ==nums[i-1]) continue;
        int left = i+1, right = len-1;
        while (left < right) {
            if(nums[i] + nums[left] + nums[right] < 0)
                // 小了就前进
                left++;
            else if(nums[i] + nums[left] + nums[right] > 0)
                // 大了就后退
                right--;
            else {
              //  std::cout<< nums[i]<< nums[left++]<<nums[right--]<<std::endl;
                r0.push_back({nums[i], nums[left++], nums[right--]});
                // 过滤右边
                while (left < right && nums[left] == nums[left+1])  left++; left++;
           //     while( left < right && nums[right] == nums[right-1]) right--; right--;
            }
        }
    }
    return r0;
}

int Solution::majorityElement(vector<int> &nums) {
    std::sort(nums.begin(),nums.end());
    return nums[nums.size()/2];
}

int Solution::firstMissingPositive(vector<int> &nums) {
    std::sort(nums.begin(),nums.end());
    int minnum=1;
    for (int i : nums) {
        if(minnum == i){
            minnum++;
        }
    }
    return minnum;
}
